home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / dev / gcc / ixemul_src.lha / ixemul-41.0 / network / lrucache.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  10KB  |  378 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. char sccsid[] = "@(#)lrucache.c    5.3 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  *  lrucache.c -- LRU cache for disk-based btree pages.
  43.  *
  44.  *    This file implements an LRU cache in user space for disk-based
  45.  *    btrees.
  46.  */
  47. #include <sys/param.h>
  48. #include <stdlib.h>
  49. #include <string.h>
  50. #include <unistd.h>
  51. #include "lrucache.h"
  52.  
  53. /*
  54.  *  LRUINIT -- Initialize a new LRU cache.
  55.  *
  56.  *    There's a separate LRU cache for every open file descriptor on which
  57.  *    the user wants caching.  The desired cache size and logical page
  58.  *    size are passed in.  We try to avoid growing the cache beyond the
  59.  *    limit specified by the user, but if we cannot satisfy a block request
  60.  *    without growing the cache, we do so.
  61.  *
  62.  *    Note that the page size passed in is the logical page size for
  63.  *    use with this file descriptor, and doesn't necessarily have anything
  64.  *    to do with the underlying hardware page size.
  65.  *
  66.  *    Parameters:
  67.  *        fd -- file descriptor for this cache
  68.  *        cachesz -- number of buffers in cache (suggested)
  69.  *        pagesz -- logical page size inside this file
  70.  *        inproc -- routine to call when a buffer is read
  71.  *        outproc -- routine to call when a buffer is written
  72.  *
  73.  *    Returns:
  74.  *        Opaque pointer to the LRU cache on success, NULL on failure.
  75.  *
  76.  *    Side Effects:
  77.  *        Allocates memory for the hash table and LRU cache.  Buffers
  78.  *        are allocated on demand, later.
  79.  */
  80. LRU
  81. lruinit(fd, cachesz, pagesz, opaque, inproc, outproc)
  82.     int fd;
  83.     int cachesz;
  84.     int pagesz;
  85.     char *opaque;
  86.     int (*inproc)();
  87.     int (*outproc)();
  88. {
  89.     register LRUCACHE *l;
  90.     int nbytes;
  91.  
  92.     /* allocate the LRU cache struct */
  93.     if ((l = (LRUCACHE *) malloc((unsigned) sizeof(LRUCACHE)))
  94.         == (LRUCACHE *) NULL)
  95.         return ((LRU) NULL);
  96.  
  97.     /* allocate the hash table */
  98.     nbytes = cachesz * sizeof(CACHE_ENT *);
  99.     if ((l->lru_cache = (CACHE_ENT **) malloc((unsigned) nbytes))
  100.         == (CACHE_ENT **) NULL) {
  101.         (void) free((char *) l);
  102.         return ((LRU) NULL);
  103.     }
  104.  
  105.     /* init memory */
  106.     bzero((char *) (l->lru_cache), (size_t) nbytes);
  107.     l->lru_fd = fd;
  108.     l->lru_psize = pagesz;
  109.     l->lru_csize = cachesz;
  110.     l->lru_cursz = 0;
  111.     l->lru_opaque = opaque;
  112.     l->lru_head = l->lru_tail = (LRU_ENT *) NULL;
  113.     l->lru_inproc = inproc;
  114.     l->lru_outproc = outproc;
  115.  
  116.     return ((LRU) l);
  117. }
  118.  
  119. /*
  120.  *  LRUGET -- Get a buffer from an LRU cache.
  121.  *
  122.  *    If the buffer is not in the cache at present, this routine will
  123.  *    instantiate it from the file.  This REQUIRES that the desired
  124.  *    block actually be on disk; we don't do non-blocking reads, so
  125.  *    if it's not actually out there, this routine won't return for
  126.  *    a very long time.  In order to instantiate a new buffer, use
  127.  *    lrugetnew().
  128.  *
  129.  *    Parameters:
  130.  *        lru -- the LRU cache to use.
  131.  *        pgno -- the logical block number to get.
  132.  *        nread -- pointer to an int, in which the number of bytes
  133.  *             read is returned.
  134.  *
  135.  *    Returns:
  136.  *        (char *) pointer to the buffer for the desired block.  The
  137.  *        number of bytes actually read is returned in *nread.
  138.  *
  139.  *    Warnings:
  140.  *        The requested buffer is locked down until the user does
  141.  *        an explicit lrurelease() on it.
  142.  */
  143.  
  144. char *
  145. lruget(lru, pgno, nread)
  146.     LRU lru;
  147.     int pgno;
  148.     int *nread;
  149. {
  150.     LRUCACHE *l = (LRUCACHE *) lru;
  151.     CACHE_ENT *ce;
  152.     LRU_ENT *lruent;
  153.     char *buffer;
  154.     long pos;
  155.  
  156.     /* is it already in the cache? */
  157.     if ((ce = lruhashget(l, pgno)) != (CACHE_ENT *) NULL) {
  158.  
  159.         /* yes, move it to the head and return it */
  160.         lruent = ce->c_lruent;
  161.         lruent->l_flags &= ~F_FREE;
  162.         lruhead(l, ce->c_lruent);
  163.         *nread = l->lru_psize;
  164.         return (ce->c_lruent->l_buffer);
  165.     }
  166.  
  167.     /* not there, get a free page */
  168.     if ((buffer = lrugetpg(l, pgno, nread, lruget)) == (char *) NULL)
  169.         return ((char *) NULL);
  170.  
  171.     /* okay, got a buffer -- fill it */
  172.     pos = (long) (l->lru_psize * pgno);
  173.     if (lseek(l->lru_fd, pos, L_SET) != pos)
  174.         return ((char *) NULL);
  175.  
  176.     *nread = read(l->lru_fd, buffer, l->lru_psize);
  177.  
  178.     if (l->lru_inproc)
  179.         (*(l->lru_inproc))(buffer, l->lru_opaque);
  180.  
  181.     return (buffer);
  182. }
  183.  
  184. /*
  185.  *  LRUGETNEW -- Get a page for a new block in an LRU cache.
  186.  *
  187.  *    This routine allows users to instantiate pages for a file if they
  188.  *    don't exist on disk yet.  It's used to make a file bigger.
  189.  *
  190.  *    Parameters:
  191.  *        lru -- the LRU cache to use
  192.  *        pgno -- the (new) logical page number to instantiate
  193.  *        nread -- ptr to int to get number of bytes read (this is
  194.  *             guaranteed to be zero, since the page isn't on disk)
  195.  *
  196.  *    Returns:
  197.  *        Pointer to a buffer for the associated page, or NULL on
  198.  *        failure.
  199.  *
  200.  *    Warnings:
  201.  *        The associated buffer is locked down until the user
  202.  *        explicitly does an lrurelease() on it.
  203.  */
  204.  
  205. char *
  206. lrugetnew(lru, pgno, nread)
  207.     LRU lru;
  208.     int pgno;
  209.     int *nread;
  210. {
  211.     LRUCACHE *l = (LRUCACHE *) lru;
  212.  
  213.     *nread = 0;
  214.     return (lrugetpg(l, pgno, nread, lrugetnew));
  215. }
  216.  
  217. /*
  218.  *  LRUFLUSH -- flush an LRU page to disk.
  219.  *
  220.  *    This routine forces a page to disk.  Users should use lruwrite(),
  221.  *    which simply marks a page dirty and does late writing.
  222.  *
  223.  *    Parameters:
  224.  *        l -- LRU cache
  225.  *        lruent -- the LRU cache entry whose page we should flush
  226.  *
  227.  *    Returns:
  228.  *        Zero on success, -1 on failure.
  229.  */
  230.  
  231. lruflush(l, lruent)
  232.     LRUCACHE *l;
  233.     LRU_ENT *lruent;
  234. {
  235.     long pos;
  236.  
  237.     if (l->lru_outproc)
  238.         (*(l->lru_outproc))(lruent->l_buffer, l->lru_opaque);
  239.  
  240.     pos = (long) (l->lru_psize * lruent->l_pgno);
  241.     if (lseek(l->lru_fd, pos, L_SET) != pos)
  242.         return (-1);
  243.     if (write(l->lru_fd, lruent->l_buffer, l->lru_psize) != l->lru_psize)
  244.         return (-1);
  245.  
  246.     if (l->lru_inproc)
  247.         (*(l->lru_inproc))(lruent->l_buffer, l->lru_opaque);
  248.  
  249.     lruent->l_flags &= ~F_DIRTY;
  250.     return (0);
  251. }
  252.  
  253. /*
  254.  *  LRUWRITE -- Mark an LRU cache buffer dirty
  255.  *
  256.  *    This routine is how users should move their changes to disk.  The
  257.  *    cache code marks the associated buffer dirty, and flushes it to
  258.  *    disk if we need to reuse the buffer for some other page.
  259.  *
  260.  *    Parameters:
  261.  *        lru -- LRU cache
  262.  *        pgno -- page number to flush
  263.  *
  264.  *    Returns:
  265.  *        Zero on success, -1 on failure.
  266.  */
  267.  
  268. int
  269. lruwrite(lru, pgno)
  270.     LRU lru;
  271.     int pgno;
  272. {
  273.     LRUCACHE *l = (LRUCACHE *) lru;
  274.     CACHE_ENT *ce;
  275.  
  276.     if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
  277.         return (-1);
  278.  
  279.     /* mark the entry dirty */
  280.     ce->c_lruent->l_flags |= F_DIRTY;
  281.  
  282.     return (0);
  283. }
  284.  
  285. /*
  286.  *  LRUSYNC -- Flush all changes to disk
  287.  *
  288.  *    This routine allows users to force all changes to buffers currently
  289.  *    in memory to disk.  This is expensive.
  290.  *
  291.  *    Parameters:
  292.  *        lru -- LRU cache to flush
  293.  *
  294.  *    Returns:
  295.  *        Zero on success, -1 on failure
  296.  *
  297.  *    Side Effects:
  298.  *        After this call, all buffers are clean.
  299.  */
  300.  
  301. int
  302. lrusync(lru)
  303.     LRU lru;
  304. {
  305.     LRUCACHE *l = (LRUCACHE *) lru;
  306.     LRU_ENT *le;
  307.  
  308.     for (le = l->lru_head; le != (LRU_ENT *) NULL; le = le->l_next)
  309.         if (le->l_flags & F_DIRTY)
  310.             if (lruflush(l, le) < 0)
  311.                 return (-1);
  312.     return (0);
  313. }
  314.  
  315. /*
  316.  *  LRURELEASE -- Release a buffer in the LRU cache for reuse
  317.  *
  318.  *    When the user does an lruget() or lrugetnew(), the buffer we return
  319.  *    is locked down, to guarantee that it's not reused while the user
  320.  *    still needs it.  Once a buffer is no longer needed, it should be
  321.  *    released (via this routine) so that we can use it for other pages
  322.  *    if necessary.
  323.  *
  324.  *    Parameters:
  325.  *        lru -- LRU cache
  326.  *        pgno -- page number of buffer to release
  327.  *
  328.  *    Returns:
  329.  *        Zero on success, -1 on failure
  330.  */
  331.  
  332. int
  333. lrurelease(lru, pgno)
  334.     LRU lru;
  335.     int pgno;
  336. {
  337.     LRUCACHE *l = (LRUCACHE *) lru;
  338.     CACHE_ENT *ce;
  339.  
  340.     if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
  341.         return (-1);
  342.     ce->c_lruent->l_flags |= F_FREE;
  343.     return (0);
  344. }
  345.  
  346. /*
  347.  *  LRUFREE -- Free an entire LRU cache
  348.  *
  349.  *    This routine releases an LRU cache.  The cache should not be
  350.  *    used again.
  351.  *
  352.  *    Parameters:
  353.  *        lru -- LRU cache to free
  354.  *
  355.  *    Returns:
  356.  *        None.
  357.  *
  358.  *    Side Effects:
  359.  *        Frees a lot of memory.
  360.  */
  361.  
  362. void
  363. lrufree(lru)
  364.     LRU lru;
  365. {
  366.     LRUCACHE *l = (LRUCACHE *) lru;
  367.     LRU_ENT *le;
  368.     LRU_ENT *sle;
  369.  
  370.     for (le = l->lru_head; le != (LRU_ENT *) NULL; ) {
  371.         free((char *) (le->l_buffer));
  372.         sle = le;
  373.         le = le->l_next;
  374.         free((char *) sle);
  375.     }
  376.     free ((char *) l);
  377. }
  378.